package sort.leetcode;

public class Num148排序链表 {
    public ListNode sortList(ListNode head) {
        if (head==null||head.next==null){
            return head;
        }
        // 找到链表的中间节点，拆分
        ListNode mid=middle(head);
        ListNode x = head;
        while (x.next!=mid){
            x=x.next;
        }
        // x.next = mid,x就是中间节点的前驱，第一个链表的尾节点
        x.next=null;
        // 先把左右两个子链表排好序
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(mid);
        // 合并这两个子链表即可
        return merge(l1,l2);

    }

    private ListNode merge(ListNode l1, ListNode l2) {
        // 递归法
//        if (l1==null){
//            return l2;
//        }
//        if (l2==null){
//            return l1;
//        }
//        if (l1.val<=l2.val){
//            l1.next=merge(l1.next,l2);
//            return l1;
//        }else {
//            l2.next=merge(l1,l2.next);
//            return l2;
//        }
        // 迭代法
        ListNode dummyHead = new ListNode();
        ListNode tail = dummyHead;
        while (l1!=null&&l2!=null){
            if (l1.val<=l2.val){
                tail.next=l1;
                tail=l1;
                l1=l1.next;
            }else {
                tail.next=l2;
                tail=l2;
                l2=l2.next;
            }
        }
        if (l1!=null){
            tail.next=l1;
        }else {
            tail.next=l2;
        }
        return dummyHead.next;
    }

    private ListNode middle(ListNode head) {
        ListNode fir = head,sec = head;
        while (fir!=null&&fir.next!=null){
            fir=fir.next.next;
            sec=sec.next;
        }
        return sec;
    }
}
